# Python 2.6.4
# Project Euler, Common functions
# Copyright 2010 Talha Zaman

def isprime(n):
    from math import sqrt
    if n<=1: return False
    if n%2==0 and n!=2: return False
    if n%3==0 and n!=3: return False
    sn = int(sqrt(n))+2
    for i in range(5,sn,6):
        if n%i==0: return False
        if n%(i+2)==0: return False
    return True

def sieveprimes(limit):
    from math import sqrt
    sieve = [False for i in range(0, limit/2)]
    sieve[0] = True
    lim = int(sqrt(limit))+1
    for i in range(3,lim,2):
        if sieve[i/2]: continue
        for j in range(i*i, limit, i*2):
            sieve[j/2] = True
    return [2] + [(x<<1)+1 for x in range(limit/2) if not sieve[x]]

def gcd(a, b):
    if a<b: a, b = b, a
    while a%b: a, b = b, a%b
    return b

def PPT():
    uv = 3
    while True:
        for u in range(1,1+uv/2):
            v = uv - u
            if gcd(u, v)!=1: continue
            yield sorted([v**2-u**2, 2*u*v, v**2+u**2])
        uv += 2

def fac(n): return reduce(lambda x,y:x*y, range(1, n+1), 1)

def nCk(n, k):
    a, b = sorted([k, n-k])
    up = reduce(lambda x,y:x*y, range(b+1, n+1), 1)
    down = reduce(lambda x,y:x*y, range(2, a+1), 1)
    return up/down

def perms(s, l, r=True):
    if l<=1: return [d for d in s]
    p = []
    for i in range(len(s)):
        subs = perms(s[:i] + s[i+1:], l-1, r) if r else perms(s, l-1, r)
        for j in subs: p.append(s[i] + j)
    return p

def listperms(s, l, r=True):
    if l<=1: return [[d] for d in s]
    p = []
    for i in range(len(s)):
        subs = listperms(s[:i] + s[i+1:], l-1, r) if r else listperms(s, l-1, r)
        for j in subs: p.append([s[i]] + j)
    return p

def stopwatch():
    from time import clock
    start = clock()
    last = start
    yield None
    while True:
        curr = clock()
        print "Interval: ", curr-last
        print "Total: ", curr-start
        last = curr
        yield None

def timed(func):
    from time import clock
    def timewrap(*args):
        start = clock()
        ans = func(*args)
        curr = clock()
        print "%s took %f sec"%(func.func_name, curr-start)
        return ans
    timewrap.func_name = func.func_name
    return timewrap

def memoized(func):
    cache = {}
    def memowrap(*args):
        key = (func, args)
        try:
            ans = cache[key]
        except KeyError:
            ans = cache[key] = func(*args)
        return ans
    memowrap.func_name = func.func_name
    return memowrap
